2590. Space Exploration

Farmer John's cows have finally blasted off from earth and are now floating around space in their Moocraft. The cows want to reach their fiery kin on Jupiter’s moon of Io, but to do this they must first navigate through the dangerous asteroid belt.

Bessie is piloting the craft through this treacherous n * n sector of space. Asteroids in this sector comprise some number of 1 * 1 squares of space-rock connected along their edges (two squares sharing only a corner count as two distinct asteroids). Please help Bessie maneuver through the field by counting the number of distinct asteroids in the entire sector.

Consider the 10 * 10 space shown below on the left. The ‘*’ represent asteroid chunks, and each ‘.’ represents a .vast void of empty space. The diagram on the right shows an arbitrary numbering applied to the asteroids.

It's easy to see there are 7 asteroids in this sector.

Input. The first line contains integer n (1 ≤ n ≤ 1000). Starting from the second line the i + 1-th line contains i-th row of the asteroid field: n characters.

Output. Print the number of asteroids in the field.

Sample input	Sample output
10 ...**..... .*........ ......*... ...*..*... ..*****... ...*...... ....***... .*..***... .....*...* ..*.......	7

SOLUTION

depth first search

Algorithm analysis

Using the depth first search, find the number of asteroids. It equals to the number of connected components specified by the characters ‘*’.

Example

Input grid contains 7 asteroids.

Algorithm realization

Declare a two-dimensional array, in which we will contain a field with asteroids.

#define MAX 1001

char m[MAX][MAX];

Depth first search on a grid starting from the cell (i, j).

void dfs(int i, int j)

{

if ((i < 0) || (i >= n) || (j < 0) || (j >= n)) return;

if (m[i][j] == '.') return;

m[i][j] = '.';

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

The main part of the program. Read the input data.

scanf("%d\n",&n);

for(i = 0; i < n; i++) gets(m[i]);

Find the number of asteroids.

c = 0;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (m[i][j] == '*')

{

dfs(i,j);

c++;

}

Print the answer.

printf("%d\n",c);